Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Notice that you should not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range
[0, 104]. -105 <= Node.val <= 105posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Average Rating: 4.44 (94 votes)
Approach 1: Hash Table
Intuition
If we keep track of the nodes that we've seen already in a Set, we can
traverse the list and return the first duplicate node.
Algorithm
First, we allocate a Set to store ListNode references. Then, we traverse
the list, checking visited for containment of the current node. If the node
has already been seen, then it is necessarily the entrance to the cycle. If
any other node were the entrance to the cycle, then we would have already
returned that node instead. Otherwise, the if condition will never be
satisfied, and our function will return null.
The algorithm necessarily terminates for any list with a finite number of
nodes, as the domain of input lists can be divided into two categories:
cyclic and acyclic lists. An acyclic list resembles a null-terminated chain
of nodes, while a cyclic list can be thought of as an acyclic list with the
final null replaced by a reference to some previous node. If the while
loop terminates, we return null, as we have traversed the entire list
without encountering a duplicate reference. In this case, the list is
acyclic. For a cyclic list, the while loop will never terminate, but at
some point the if condition will be satisfied and cause the function to
return.
Complexity Analysis
-
Time complexity : O(n)
For both cyclic and acyclic inputs, the algorithm must visit each node exactly once. This is transparently obvious for acyclic lists because the nth node points to
null, causing the loop to terminate. For cyclic lists, theifcondition will cause the function to return after visiting the nth node, as it points to some node that is already invisited. In both cases, the number of nodes visited is exactly n, so the runtime is linear in the number of nodes. -
Space complexity : O(n)
For both cyclic and acyclic inputs, we will need to insert each node into the
Setonce. The only difference between the two cases is whether we discover that the "last" node points tonullor a previously-visited node. Therefore, because theSetwill contain n distinct nodes, the memory footprint is linear in the number of nodes.
Approach 2: Floyd's Tortoise and Hare
Intuition
What happens when a fast runner (a hare) races a slow runner (a tortoise) on a circular track? At some point, the fast runner will catch up to the slow runner from behind.
Algorithm
Floyd's algorithm is separated into two distinct phases. In the first
phase, it determines whether a cycle is present in the list. If no cycle is
present, it returns null immediately, as it is impossible to find the
entrance to a nonexistant cycle. Otherwise, it uses the located "intersection
node" to find the entrance to the cycle.
Phase 1
Here, we initialize two pointers - the fast hare and the slow tortoise.
Then, until hare can no longer advance, we increment tortoise once and
hare twice.[1] If, after advancing them, hare and tortoise point to
the same node, we return it. Otherwise, we continue. If the while loop
terminates without returning a node, then the list is acyclic, and we return
null to indicate as much.
To see why this works, consider the image below:
Here, the nodes in the cycle have been labelled from 0 to C−1, where
C is the length of the cycle. The noncyclic nodes have been labelled from
−F to -1, where F is the number of nodes outside of the cycle. After
F iterations, tortoise points to node 0 and hare points to some node
h, where F≡h(modC). This is because hare traverses 2F
nodes over the course of F iterations, exactly F of which are in the
cycle. After C−h more iterations, tortoise obviously points to node
C−h, but (less obviously) hare also points to the same node. To see why,
remember that hare traverses 2(C−h) from its starting position of h:
h+2(C−h)=2C−h≡C−h(modC)
Therefore, given that the list is cyclic, hare and tortoise will
eventually both point to the same node, known henceforce as the
intersection.
Phase 2
Given that phase 1 finds an intersection, phase 2 proceeds to find the node
that is the entrance to the cycle. To do so, we initialize two more pointers:
ptr1, which points to the head of the list, and ptr2, which points to
the intersection. Then, we advance each of them by 1 until they meet; the
node where they meet is the entrance to the cycle, so we return it.
Use the diagram below to help understand the proof of this approach's correctness.
We can harness the fact that hare moves twice as quickly as tortoise to
assert that when hare and tortoise meet at node h, hare has
traversed twice as many nodes. Using this fact, we deduce the following:
To compute the intersection point, let's note that the hare has traversed twice as many nodes as the tortoise, i.e. 2d(tortoise)=d(hare), that means
2(F+a)=F+nC+a, where n is some integer.
Hence the coordinate of the intersection point is F+a=nC.
To see the entire algorithm in action, check out the animation below:
Complexity Analysis
-
Time complexity : O(n)
For cyclic lists,
hareandtortoisewill point to the same node after F+C−h iterations, as demonstrated in the proof of correctness. F+C−h≤F+C=n, so phase 1 runs in O(n) time. Phase 2 runs for F<n iterations, so it also runs in O(n) time.For acyclic lists,
harewill reach the end of the list in roughly 2n iterations, causing the function to return before phase 2. Therefore, regardless of which category of list the algorithm receives, it runs in time linearly proportional to the number of nodes. -
Space complexity : O(1)
Floyd's Tortoise and Hare algorithm allocates only pointers, so it runs with constant overall memory usage.
Footnotes
It is sufficient to check only
harebecause it will always be ahead oftortoisein an acyclic list. ↩︎
Last Edit: January 22, 2020 12:53 PM
F = b is incorrect, which is obvious when F is very large and C is very small. Rather, from 2*d(tortoise) = d(hare), we have 2(F+a) = F+nC+a, for some integer n, so F+a = nC, or F = nC-a. In phase two, you dispatch another tortoise from the head of the list, and slow down the hare in the cycle to advance one node per step. After F steps the tortoise will travel F nodes, and the hare will travel F=nC-a nodes. The hare started at F+a = F+a%C, so the hare's position after F steps is F+(a+F)%C = F+(a+nC-a)%C = F. So the tortoise and the (slow) hare will meet at the start of the cycle.
March 12, 2019 7:33 PM
Please, fix your output statement in the description....I felt like I need to output a string.
Why do you put something like "Output: tail connects to node index 0" when you actually want "Node"?
Last Edit: September 20, 2018 9:23 AM
I don't think this solution is faithfulness enough. The F should be equals to nC+b, (n>=0)rather than b, since F may be very large, but b may be very small.
But the method still works well.
June 17, 2019 12:08 AM
F != h (mod C) . its other way around h = F (mod C). Please fix it.
May 14, 2020 9:45 AM
Can someone explain why the intersection point is naturally the point that its distance to the cycle entrance is the same as the distance from the beginning to the cycle entrance?
The proof of F=b is wrong, instead it should be F=b (mod C)
If you prefer simple math and don't care about modular arithmetic for a formal proof, I personally understand why Floyd's algorithm works using this simple case.
Algorithm: Assume non-cyclic length N and cyclic length M with index [0,M-1]
<- N -> 1. When slow enters the cycle at 0 (◎), fast is at N (■)
s
□-□-□-□-◎-□-□-□ 2. Fast is M-N behind, so they will meet at M-N (※)
| |
□ M ■ f 3. Cycle entrance is now M-(M-N) = N away, so if we
| | make one pointer start over and both at slow speed,
□-□-※-□ they will guarantee to meet again at 0 (◎)
meet
There is actually an easier way to understand how the phase 2 works. From the explanation of phase 1, we know if it is cyclic then hare and tortoise will meet at (C- h) mod C. Therefore, the distance between intersection and the entrance is "h mod C". On the other hand, the distance between HEAD node and the entrance node is F, and we had the assumption which is F = h mod C. Therefore the next meeting point will be the entrance node.
Why does it not work when I start with the slow pointer equal to the head and the fast pointer equal to head.next? It worked for the Linked-List-Cycle 1 problem but here it gives me TLE, and the solution works when I start both pointers at the head and do the equality check after moving the pointers.
For reference this is the TLE code for this problem:
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
if(slow == fast){
fast = head;
while(fast != slow){
slow = slow.next;
fast = fast.next;
}
return fast;
}
slow = slow.next;
fast = fast.next.next;
}
return null;
}
while a similar idea for Linked List Cycle 1 works fine:
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode fastPointer = head.next;
ListNode slowPointer = head;
while(fastPointer != null && fastPointer.next != null){
if(fastPointer == slowPointer) return true;
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
}
return false;
}
}
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/15/2021 09:12 | Accepted | 0 ms | 7.6 MB | cpp |
| 07/27/2020 08:51 | Accepted | 8 ms | 7.7 MB | cpp |
| 07/27/2020 08:50 | Wrong Answer | N/A | N/A | cpp |
x
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* getIntersection(ListNode *head) { ListNode *fast = head; ListNode *slow = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if(fast == slow) return slow; } return NULL; } ListNode *detectCycle(ListNode *head) { if(head == NULL) return NULL; ListNode *intersect = getIntersection(head); if(intersect == NULL) return NULL; ListNode *p1 = head; ListNode *p2 = intersect; while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; }};